(人･∀･)
嗨，我是wec，今天是DAY 24。

🔎 題目難度與描述

難度：MEDIUM

題目描述：

在一個 m x n 的網格中，每個單元格可以有以下三種狀態之一：
0 代表空單元格。
1 代表新鮮橘子。
2 代表腐爛的橘子。
每一分鐘所有相鄰（上下左右）的新鮮橘子會被腐爛的橘子感染變成腐爛的。請計算最少需要多少分鐘，才能讓所有的新鮮橘子都變成腐爛的。如果不可能讓所有的新鮮橘子都變成腐爛的，返回 -1。

🔎 解題思路＆程式碼

1️⃣ 佇列

第1步： 先遍歷整個網格，把所有腐爛的橘子加入佇列，並記錄新鮮橘子的總數。
第2步： 每分鐘從佇列中取出當前所有腐爛橘子，將其四周的新鮮橘子腐爛，並加入佇列。
第3步： 每次擴展都會增加分鐘數，直到佇列中沒有新鮮橘子為止。如果最後還有新鮮橘子沒被腐爛，返回 -1。
程式碼：

def oranges_rotting(grid)
  rows, cols = grid.size, grid[0].size
  queue = []
  fresh_count = 0

  rows.times do |i|
    cols.times do |j|
      if grid[i][j] == 2
        queue << [i, j]
      elsif grid[i][j] == 1
        fresh_count += 1
      end
    end
  end
  
  return 0 if fresh_count == 0
  
  directions = [[0,1], [1,0], [0,-1], [-1,0]]
  minutes = 0
  
  while !queue.empty?
    next_queue = []
    
    queue.each do |x, y|
      directions.each do |dx, dy|
        nx, ny = x + dx, y + dy
        if nx >= 0 && nx < rows && ny >= 0 && ny < cols && grid[nx][ny] == 1
          grid[nx][ny] = 2 
          fresh_count -= 1
          next_queue << [nx, ny]
        end
      end
    end
    
    queue = next_queue
    minutes += 1 unless queue.empty?
  end
  
  fresh_count == 0 ? minutes : -1
end

🔎 總結

時間複雜度

佇列： O(n*m)， m 是行數，n 是列數。
➡️ 看到題目敘述應該不難理解就是要用BFS解題，概念就像病毒蔓延，不需要逐一檢查每個橘子，只需要找到腐爛的橘子然後向外擴展就可以了，也因為這樣，遍歷只需要一次就可以解決問題，所以這樣的方法可以在合理的時間內解決較大的網格ヽ(^ω^)ﾉ 。

那麽，以上就是今天的內容！

相信IT人動腦時都要吃點東西，所以今天邊寫邊喝一沐日的粉粿桂花檸檬。
明天要說：Ruby精選刷題！Medium路跑D-17(>∀･)⌒☆